/*
*
给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。

你的得分方式为：每一行 中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分 增加 points[r][c] 。

然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 r 和 r + 1 （其中 0 <= r < m - 1），选中坐标为 (r, c1) 和 (r + 1, c2) 的格子，你的总得分 减少 abs(c1 - c2) 。

请你返回你能得到的 最大 得分。

abs(x) 定义为：

如果 x >= 0 ，那么值为 x 。
如果 x < 0 ，那么值为 -x 。

示例 1：

输入：points = [[1,2,3],[1,5,1],[3,1,1]]
输出：9
解释：
蓝色格子是最优方案选中的格子，坐标分别为 (0, 2)，(1, 1) 和 (2, 0) 。
你的总得分增加 3 + 5 + 3 = 11 。
但是你的总得分需要扣除 abs(2 - 1) + abs(1 - 0) = 2 。
你的最终得分为 11 - 2 = 9 。
示例 2：

输入：points = [[1,5],[2,3],[4,2]]
输出：11
解释：
蓝色格子是最优方案选中的格子，坐标分别为 (0, 1)，(1, 1) 和 (2, 0) 。
你的总得分增加 5 + 3 + 4 = 12 。
但是你的总得分需要扣除 abs(1 - 1) + abs(1 - 0) = 1 。
你的最终得分为 12 - 1 = 11 。

提示：

m == points.length
n == points[r].length
1 <= m, n <= 105
1 <= m * n <= 105
0 <= points[r][c] <= 105

  - @author ala
  - @date 2024-09-26 10:51
*/
package main

import (
	"fmt"
	"math"
)

func main() {
	points := [][]int{{1, 2, 3}, {1, 5, 1}, {3, 1, 1}}

	fmt.Println(maxPoints(points))
}

/**
 *	1）(i,j)点的得分：v = points[i][j] + max(dp[i-1][k] - |k - j|)
 *		当 k <= j 时：v = points[i][j] + max(dp[i-1][k] - j + k)
 *					   = points[i][j] - j + max(dp[i-1][k] + k)
 *		当 k > j 时：v = points[i][j] + max(dp[i-1][k] - k + j)
 *					  = points[i][j] + j + max(dp[i-1][k] - k)
 *	2）定义dp[j][0 | 1]表示：
 *		dp[j][0]：上一行[j]列的最大得分 + k
 *		dp[j][1]：上一行[j]列的最大得分 - k
 *	   	L[j]表示从左往右 dp[j][0] 的最大值
 *		R[j]表示从右往左 dp[j][1] 的最大值
 *	3）v = max(points[i][j] - j + L[j], points[i][j] + j + R[j])
 */
func maxPoints(points [][]int) int64 {
	M, N := len(points), len(points[0])
	dp, L, R := make([][]int, N), make([]int, N), make([]int, N)
	res := 0
	for i := range dp {
		dp[i] = make([]int, 2)
	}
	for j, v := range points[0] {
		dp[j][0], dp[j][1] = v+j, v-j
		res = max(res, v)
	}
	if M == 1 {
		return int64(res)
	}
	maxLR(dp, L, R)

	for i := 1; i < M; i++ {
		for j := 0; j < N; j++ {
			v := points[i][j]
			mx := max(v-j+L[j], v+j+R[j])
			res = max(res, mx)

			dp[j][0] = mx + j
			dp[j][1] = mx - j
		}
		maxLR(dp, L, R)
	}
	return int64(res)
}
func maxLR(dp [][]int, L, R []int) {
	lm, rm := math.MinInt, math.MinInt
	for i := 0; i < len(dp); i++ {
		lm = max(lm, dp[i][0])
		L[i] = lm

		j := len(dp) - 1 - i
		rm = max(rm, dp[j][1])
		R[j] = rm
	}
}
